from collections import deque
from typing import *
from math import inf


class Solution:
    def numBusesToDestination(
        self, routes: List[List[int]], source: int, target: int
    ) -> int:
        if source == target:
            return 0
        n = len(routes)
        st = DefaultDict(list)
        for i, arr in enumerate(routes):
            for r in arr:
                st[r].append(i)
        visit = [inf] * n
        q = deque()
        for v in st[source]:
            visit[v] = 1
            q.append(v)

        while q:
            v = q.popleft()
            if v in st[target]:
                return visit[v]
            for nxt in routes[v]:
                for nt in st[nxt]:
                    if visit[v] + 1 < visit[nt]:
                        visit[nt] = visit[v] + 1
                        q.append(nt)

        return -1


s = Solution()
print(s.numBusesToDestination(routes=[[1, 2, 7], [3, 6, 7]], source=1, target=6))
